# -*- coding: utf-8 -*-
# @Time    : 2024/6/7 15:59
# @Author  : yujiahao
# @File    : 09_dict.py
# @description:Python中的字典（dict）



"""

 - 列表可以存储大量的数据类型，但是只能按照顺序存储，数据与数据之间关联性不强。
 - 所以咱们需要引入一种容器型的数据类型，解决上面的问题，这就需要dict字典。
 - 字典(dict)是python中唯⼀的⼀个映射类型.他是以{ }括起来的键值对组成.
 - 在dict中key是【唯一并且不可变的】.在保存的时候, 根据key来计算出⼀个内存地址. 然后将key-value保存在这个地址中.
 - 这种算法被称为hash算法, 所以, 切记, 在dict中存储的key-value中的key必须是可hash的
 - 可以改变的都是不可哈希的, 那么可哈希就意味着不可变. 这个是为了能准确的计算内存地址⽽规定的.
 - 已知的可哈希(不可变)的数据类型: int, str, tuple, bool 不可哈希(可变)的数据类型: list, dict, set
 - 语法:{'key1':1,'key2':2} 这玩意长得像 HashMap

注意:dict保存的数据不是按照我们添加进去的顺序保存的. 是按照hash表的顺序保存的. ⽽hash表 不是连续的. 所以不能进⾏切片⼯作. 它只能通过key来获取dict中的数据

Java Map vs Python 字典 vs Scala Map

1. 定义和结构：
   - Java Map：
     - 定义：Map 是一个接口，表示键值对的映射。键和值可以是任何对象类型。
     - 结构：常见的实现有 HashMap、TreeMap 和 LinkedHashMap。
     - 创建：
       import java.util.HashMap;
       Map<String, Integer> map = new HashMap<>();
       // TreeMap 和 LinkedHashMap 的创建方式类似
       import java.util.TreeMap;
       Map<String, Integer> treeMap = new TreeMap<>();
       import java.util.LinkedHashMap;
       Map<String, Integer> linkedHashMap = new LinkedHashMap<>();

   - Python 字典：
     - 定义：字典是键值对的无序集合，键必须是不可变类型（如字符串、数字或元组），值可以是任意类型。
     - 结构：Python 内置的 dict 类型。
     - 创建：
       my_dict = {"key1": 1, "key2": 2}
       # 使用 dict() 函数创建
       my_dict = dict(key1=1, key2=2)
       # 空字典
       empty_dict = {}

   - Scala Map：
     - 定义：Map 是键值对的集合，键和值可以是任何类型。
     - 结构：Scala 提供不可变 Map（默认）和可变 Map 两种类型。
     - 创建：
       import scala.collection.mutable
       val immutableMap = Map("key1" -> 1, "key2" -> 2)
       val mutableMap = mutable.Map("key1" -> 1, "key2" -> 2)
       # 空 Map
       val emptyImmutableMap = Map.empty[String, Int]
       val emptyMutableMap = mutable.Map.empty[String, Int]

2. 使用方法：
   - Java Map：
     - 插入和更新：
       map.put("key1", 1);
       map.put("key2", 2);
       map.put("key1", 10);  // 更新 key1 的值
     - 访问：
       Integer value = map.get("key1");
       // 检查键是否存在
       if (map.containsKey("key1")) {
           System.out.println("Key1 exists");
       }
     - 删除：
       map.remove("key1");
     - 遍历：
       for (Map.Entry<String, Integer> entry : map.entrySet()) {
           System.out.println(entry.getKey() + ": " + entry.getValue());
       }
       // Java 8 及以上版本可以使用 forEach
       map.forEach((key, value) -> System.out.println(key + ": " + value));

   - Python 字典：
     - 插入和更新：
       my_dict["key1"] = 1
       my_dict["key2"] = 2
       my_dict["key1"] = 10  # 更新 key1 的值
     - 访问：
       value = my_dict["key1"]
       # 使用 get 方法避免 KeyError
       value = my_dict.get("key1", default_value)
     - 删除：
       del my_dict["key1"]
       # 使用 pop 方法删除并返回值
       value = my_dict.pop("key1", default_value)
     - 遍历：
       for key, value in my_dict.items():
           print(f"{key}: {value}")
       # 仅遍历键
       for key in my_dict.keys():
           print(key)
       # 仅遍历值
       for value in my_dict.values():
           print(value)

   - Scala Map：
     - 插入和更新：
       val immutableMap = immutableMap + ("key1" -> 10)  // 不可变 Map 更新
       mutableMap("key1") = 10  // 可变 Map 更新
     - 访问：
       val value = immutableMap("key1")
       // 使用 get 方法避免 NoSuchElementException
       val valueOption = immutableMap.get("key1")
     - 删除：
       val immutableMap = immutableMap - "key1"  // 不可变 Map 删除
       mutableMap -= "key1"  // 可变 Map 删除
     - 遍历：
       for ((key, value) <- immutableMap) {
           println(s"$key: $value")
       }
       // 使用 foreach 方法
       immutableMap.foreach { case (key, value) => println(s"$key: $value") }

3. 应用：
   - Java Map：
     - 常用于需要快速查找、插入和删除键值对的场景。
     - 适用于缓存、索引、配置管理等场景。
     - HashMap 适用于大多数场景，具有快速访问和插入性能。
     - TreeMap 适用于需要按键排序的场景。
     - LinkedHashMap 适用于需要维护插入顺序的场景。

   - Python 字典：
     - 广泛用于存储和管理数据，特别是在数据处理和分析中。
     - 适用于配置文件、数据序列化、快速查找和数据聚合等场景。
     - 字典的灵活性和易用性使其在数据科学和机器学习中非常流行。

   - Scala Map：
     - 常用于函数式编程中的不可变数据结构。
     - 适用于并发编程、数据处理和分布式系统中。
     - 不可变 Map 适用于需要高并发和线程安全的场景。
     - 可变 Map 适用于需要频繁更新的场景。

4. 注意事项：
   - Java Map：
     - 选择合适的 Map 实现非常重要：HashMap 适用于大多数场景，TreeMap 适用于需要排序的场景，LinkedHashMap 适用于需要维护插入顺序的场景。
     - 注意线程安全问题，必要时使用 ConcurrentHashMap。
     - 注意键和值的类型一致性，避免 ClassCastException。

   - Python 字典：
     - 键必须是不可变类型，通常使用字符串或数字。
     - 字典是无序的（在 Python 3.7 及以上版本中，字典保持插入顺序，但不应依赖此特性）。
     - 注意字典的嵌套结构，可能需要使用深拷贝（copy.deepcopy）来复制复杂的字典。

   - Scala Map：
     - 默认的 Map 是不可变的，需要可变 Map 时需显式导入 mutable 包。
     - 注意不可变 Map 的更新会返回新的 Map，而不会修改原有的 Map。
     - 在并发场景中，优先使用不可变 Map 以确保线程安全。


【附赠HashMap底层原理，Java相关喜欢问】


    1、Java HashMap 的底层原理：

        Java 8 之前：
        1. 使用一个数组存储键值对，每个数组元素是一个链表（链地址法）。
        2. 通过键的哈希值计算数组索引，将键值对存储在对应位置。
        3. 解决哈希冲突的方法是链地址法，如果多个键的哈希值相同，则这些键值对存储在同一个链表中。
        4. 当哈希表的负载因子超过设定阈值（通常为0.75）时，进行扩容操作，将所有键值对重新分配到新的更大的数组中。
        5. 在最坏情况下，链表的查找、插入和删除操作的时间复杂度为 O(n)，其中 n 是链表的长度。

        Java 8 之后：
        1. 仍然使用一个数组存储键值对，每个数组元素是一个链表或红黑树。
        2. 通过键的哈希值计算数组索引，将键值对存储在对应位置。
        3. 解决哈希冲突的方法是链地址法，但当链表长度超过阈值（默认8）时，链表会转换为红黑树，以提高性能。
        4. 当哈希表的负载因子超过设定阈值（通常为0.75）时，进行扩容操作，将所有键值对重新分配到新的更大的数组中。
        5. 红黑树在最坏情况下可以保证 O(log n) 的查找、插入和删除性能，而链表在最坏情况下是 O(n)。
        6. 通过这种改进，Java 8 之后的 HashMap 在处理大量冲突时性能更稳定。

    2、基本结构：

        数组：HashMap 底层是一个数组，每个数组元素是一个链表（在 Java 8 之前）或红黑树（在 Java 8 及之后）。
        链表：当发生哈希冲突时，多个键值对会被存储在同一个链表中。
        红黑树：为了提高性能，当链表长度超过一定阈值（默认是 8）时，链表会转换为红黑树。

    3、哈希函数：

        HashMap 使用键的 hashCode() 方法计算哈希值，然后通过哈希值确定键值对在数组中的位置。
        哈希值经过进一步处理（如高位运算）来减少哈希冲突。

    4、哈希冲突：

        当两个键的哈希值相同时，会发生哈希冲突。HashMap 通过链表或红黑树来解决哈希冲突。
        在链表中，新的键值对会被添加到链表的头部或尾部。
        在红黑树中，新的键值对会被按红黑树的规则插入。

    5、扩容机制：

        当 HashMap 中的元素数量超过一定阈值（加载因子，默认是 0.75）时，会进行扩容。
        扩容时，HashMap 会创建一个新的数组，容量是原来的两倍，然后将原数组中的所有键值对重新哈希并放入新数组中。

    6、操作复杂度：

    插入、删除和查找的平均时间复杂度是O(1)，最坏情况下（所有元素都在同一个链表或红黑树中）是O(n)。
    当链表长度超过阈值并转换为红黑树后，最坏情况下的时间复杂度为O(logn)。

    7、具体实现细节

        ① 数组和链表的定义：

            transient Node<K,V>[] table;
            static class Node<K,V> implements Map.Entry<K,V> {
                final int hash;
                final K key;
                V value;
                Node<K,V> next;
                // 构造函数和其他方法
            }
        ② 哈希值计算：

            static final int hash(Object key) {
                int h;
                return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
            }
        ③ 插入元素：

            public V put(K key, V value) {
                return putVal(hash(key), key, value, false, true);
            }

            final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
                Node<K,V>[] tab; Node<K,V> p; int n, i;
                if ((tab = table) == null || (n = tab.length) == 0)
                    n = (tab = resize()).length;
                if ((p = tab[i = (n - 1) & hash]) == null)
                    tab[i] = new Node<>(hash, key, value, null);
                else {
                    Node<K,V> e; K k;
                    if (p.hash == hash &&
                        ((k = p.key) == key || (key != null && key.equals(k))))
                        e = p;
                    else if (p instanceof TreeNode)
                        e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
                    else {
                        for (int binCount = 0; ; ++binCount) {
                            if ((e = p.next) == null) {
                                p.next = new Node<>(hash, key, value, null);
                                if (binCount >= TREEIFY_THRESHOLD - 1)
                                    treeifyBin(tab, hash);
                                break;
                            }
                            if (e.hash == hash &&
                                ((k = e.key) == key || (key != null && key.equals(k))))
                                break;
                            p = e;
                        }
                    }
                    if (e != null) {
                        V oldValue = e.value;
                        if (!onlyIfAbsent || oldValue == null)
                            e.value = value;
                        afterNodeAccess(e);
                        return oldValue;
                    }
                }
                ++modCount;
                if (++size > threshold)
                    resize();
                afterNodeInsertion(evict);
                return null;
            }

        ④ 扩容：

            final Node<K,V>[] resize() {
                Node<K,V>[] oldTab = table;
                int oldCap = (oldTab == null) ? 0 : oldTab.length;
                int oldThr = threshold;
                int newCap, newThr = 0;
                if (oldCap > 0) {
                    if (oldCap >= MAXIMUM_CAPACITY) {
                        threshold = Integer.MAX_VALUE;
                        return oldTab;
                    }
                    else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                             oldCap >= DEFAULT_INITIAL_CAPACITY)
                        newThr = oldThr << 1;
                }
                else if (oldThr > 0)
                    newCap = oldThr;
                else {
                    newCap = DEFAULT_INITIAL_CAPACITY;
                    newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
                }
                if (newThr == 0) {
                    float ft = (float)newCap * loadFactor;
                    newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                              (int)ft : Integer.MAX_VALUE);
                }
                threshold = newThr;
                @SuppressWarnings({"rawtypes","unchecked"})
                Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
                table = newTab;
                if (oldTab != null) {
                    for (int j = 0; j < oldCap; ++j) {
                        Node<K,V> e;
                        if ((e = oldTab[j]) != null) {
                            oldTab[j] = null;
                            if (e.next == null)
                                newTab[e.hash & (newCap - 1)] = e;
                            else if (e instanceof TreeNode)
                                ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                            else {
                                Node<K,V> loHead = null, loTail = null;
                                Node<K,V> hiHead = null, hiTail = null;
                                Node<K,V> next;
                                do {
                                    next = e.next;
                                    if ((e.hash & oldCap) == 0) {
                                        if (loTail == null)
                                            loHead = e;
                                        else
                                            loTail.next = e;
                                        loTail = e;
                                    }
                                    else {
                                        if (hiTail == null)
                                            hiHead = e;
                                        else
                                            hiTail.next = e;
                                        hiTail = e;
                                    }
                                } while ((e = next) != null);
                                if (loTail != null) {
                                    loTail.next = null;
                                    newTab[j] = loHead;
                                }
                                if (hiTail != null) {
                                    hiTail.next = null;
                                    newTab[j + oldCap] = hiHead;
                                }
                            }
                        }
                    }
                }
                return newTab;
            }
【总结】
    Java 中 HashMap 的底层实现通过数组、链表和红黑树的组合来存储和管理键值对。
    它通过哈希函数将键映射到数组索引，处理哈希冲突时使用链表或红黑树。扩容机制确保了 HashMap 在负载增加时仍能保持高效的性能。
    了解这些底层原理有助于更好地使用和优化 HashMap。

"""


# todo 1、字典的创建 两种方式

''' 
注意: key必须是不可变(可哈希)的. value没有要求.可以保存任意类型的数据，否则不合法
 - dic = {[1, 2, 3]: '周杰伦'} # list是可变的. 不能作为key
 - dic = {{1: 2}: "哈哈哈"} # dict是可变的. 不能作为key
 - dic = {{1, 2, 3}: '呵呵呵'} # set是可变的, 不能作为key
'''

# 1、直接创建
# my_dect = {'name': '张国荣','age':18,'gender':'male'}
# 2、使用dict()方法
my_dect = dict(name  = '张国荣', age = 18, gender = 'male')


print('''\n-----------------------------------☆☆☆分割线☆☆☆----------------------------------------\n''')

# todo 2、增

# 2.1、直接修改一条完整的数据，前提key是存在的

my_dect['name'] = '王祖贤'
my_dect['age'] = 20
my_dect['gender'] = 'female'

print(my_dect)


# 2.2、如果dict中没有出现这个key,就会将key-value组合添加到这个字典中

my_dect['job'] = '演员'
print(my_dect)


# 2.3、如果dict中没有出现过这个key-value. 可以通过setdefault设置默认值
# dict.setdefault(key, default=None)
# 当setdefault中第一个参数存在这个字典中就就不进行添加操作,否则就添加

my_dect.setdefault('我呢是默认的key，我的默认values是None')

# 如果key-values都设置了默认值，这样就是不会进行添加操作了,因为【我是默认的key】在dic这个字典中存在
my_dect.setdefault('我是默认的key','我是默认values')

print(my_dect)


print('''\n-----------------------------------☆☆☆分割线☆☆☆----------------------------------------\n''')

# todo 3、删


del my_dect["我呢是默认的key，我的默认values是None"]
print(my_dect)

print(f'pop删除有返回值,返回的是被删的值:{my_dect.pop("我是默认的key")}')
print(my_dect)

print(f'随机删除  python3.6是删除最后一个:{my_dect.popitem()}')
print(my_dect)


print('''\n-----------------------------------☆☆☆分割线☆☆☆----------------------------------------\n''')


# todo 4、改

# 两种方式
print(f'改之前：{my_dect}')

# 4.1、 当key存在就是修改对应的值,如果不存在就是添加
my_dect['age'] = 18

print(f'改之后：{my_dect}')
# 4.2、当update中的字典里没有dic中键值对就添加到dic字典中,如果有就修改里边的对应的值

# 使用另一个字典更新
update_dict = {'name': '王祖贤', 'age': 30}
my_dect.update(update_dict)
print(f'改之后：{my_dect}')

# 使用可迭代对象更新,key不存在就新增
update_items = [('name', '王祖贤'), ('age', 20), ('哇呜', '新值')]
my_dect.update(update_items)
print(f'改之后：{my_dect}')


print('''\n-----------------------------------☆☆☆分割线☆☆☆----------------------------------------\n''')

# todo 5、查

# 1、通过key访问
print(f'我是通过key值来访问values的，key不存在我可能会报错：{my_dect["name"]}')

# 2、通过get()方法访问【推荐】
print(f'我是通过get()来访问values的，key不存在我回返回None：{my_dect.get("Hi")}')

# 3、获取字典所有的键
print(f'我是获取字典所有的key:{my_dect.keys()}')

# 4、获取字典所有的值
print(f'我是获取字典所有的key:{my_dect.values()}')

# 4、获取字典的键值对
# 一个高仿列表,存放是多个元祖,元祖中第一个是字典中的键,第二个是字典中的值
print(f'我是获取字典的键值对:{my_dect.items()}')

print('''\n-----------------------------------☆☆☆分割线☆☆☆----------------------------------------\n''')

# todo 6、解构

a,b = 1,2
print(a,b)


a,b = ('Hello','World')
print(a,b)


a,b = ['Hello','Python']
print(a,b)


a,b = {'张学友':'吻别','伍佰':'啊,你说'}
print(a,b)


print('''\n-----------------------------------☆☆☆分割线☆☆☆----------------------------------------\n''')

# 做个练习，循环遍历键、值、以及键值对

for k in my_dect.keys():
    print(f'我是循环打印键\t{k}')

for v in my_dect.values():
    print(f'我是循环打印值\t{v}')

for t in my_dect.items():
    print(f'我是循环打印元组形式键值对\t{t}')

for k,v in my_dect.items():
    print(f'我是循环打印键\t{k}')
    print(f'我是循环打印值\t{v}')


print('''\n-----------------------------------☆☆☆分割线☆☆☆----------------------------------------\n''')

# todo 7、字典的嵌套
dic = {
    'name':'张柏芝',
    'age':48,
    'man':[{'name':'谢霆锋','age':38}],
    'children':['第一个熊孩子','第二个熊孩子']
}
# 获取张柏芝的男人名字

d1 = dic['man'][0]['name']
print(d1)
# 获取的孩子们
d2 = dic['children']
print(d2)
# 获取第一个孩子
d3 = dic['children'][0]
print(d3)



print('''\n-----------------------------------☆☆☆分割线☆☆☆----------------------------------------\n''')

# 趁热打铁,这个比较综合，不着急慢慢来

dic1 = {
 'name':['alex',2,3,5],
 'job':'teacher',
 'oldboy':{'alex':['python1','python2',100]}
 }

# 1，将name对应的列表追加⼀个元素’wusir’。
dic1['name'].append('wusir')
print(dic1)

# 2，将name对应的列表中的alex⾸字⺟⼤写。
dic1['name'][0] = dic1['name'][0].capitalize()
print(dic1)

# 3，oldboy对应的字典加⼀个键值对’⽼男孩’,’肖央’。
dic1['oldboy'].update({'老男孩_1':'肖央'})
dic1['oldboy']['老男孩_2'] = '王太利'
print(dic1)

# 4，将oldboy对应的字典中的alex对应的列表中的python2删除
dic1['oldboy']['alex'].remove('python2')
print(dic1)